# 72. 编辑距离
# https://leetcode-cn.com/problems/edit-distance/
# 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
#
# 你可以对一个单词进行如下三种操作：
#
# 插入一个字符
# 删除一个字符
# 替换一个字符
#
#
# 示例 1：
#
# 输入：word1 = "horse", word2 = "ros"
# 输出：3
# 解释：
# horse -> rorse (将 'h' 替换为 'r')
# rorse -> rose (删除 'r')
# rose -> ros (删除 'e')
# 示例 2：
#
# 输入：word1 = "intention", word2 = "execution"
# 输出：5
# 解释：
# intention -> inention (删除 't')
# inention -> enention (将 'i' 替换为 'e')
# enention -> exention (将 'n' 替换为 'x')
# exention -> exection (将 'n' 替换为 'c')
# exection -> execution (插入 'u')
#
#
# 提示：
#
# 0 <= word1.length, word2.length <= 500
# word1 和 word2 由小写英文字母组成
#
# 题解:
# 动态规划
# - d[i][j]为s1前i个字符和s2前j个字符的编辑距离
# - d[0][:] = 1, d[:][0] = 1, d[0][0] = 0
# - 更新
# - - if s1[i] == s2[j]: d[i+1][j+1] = d[i][j]
# - - else: d[i+1][j+1] = min(d[i][j+1]+1, d[i+1][j]+1, d[i][j]+1)
# - 最终结果: d[len(s1)][len(s2)]
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        d = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
        for i in range(1, len(word1) + 1):
            d[i][0] = i
        for j in range(1, len(word2) + 1):
            d[0][j] = j
        for i in range(len(word1)):
            for j in range(len(word2)):
                if word1[i] == word2[j]:
                    d[i + 1][j + 1] = min(d[i][j + 1] + 1, d[i + 1][j] + 1, d[i][j])
                else:
                    d[i + 1][j + 1] = min(d[i][j + 1] + 1, d[i + 1][j] + 1, d[i][j] + 1)

        return d[len(word1)][len(word2)]

    def minDistance_with_trip(self, word1: str, word2: str) -> int:
        d = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
        transit = {}

        for i in range(1, len(word1) + 1):
            d[i][0] = i
            transit[(i, 0)] = ('delete %s' % word1[0], (i, 0))
        for j in range(1, len(word2) + 1):
            d[0][j] = j
            transit[(0, j)] = ('insert %s' % word2[0], (0, j))

        for i in range(len(word1)):
            for j in range(len(word2)):
                if word1[i] == word2[j]:
                    d[i + 1][j + 1] = min(d[i][j + 1] + 1, d[i + 1][j] + 1, d[i][j])
                    transit[(i + 1, j + 1)] = transit[(i, j)]
                else:
                    d[i + 1][j + 1] = min(d[i][j + 1] + 1, d[i + 1][j] + 1, d[i][j] + 1)
                    if d[i][j + 1] + 1 == d[i + 1][j + 1]:
                        transit[(i + 1, j + 1)] = ('delete %s' % word1[i], (i, j + 1))
                    elif d[i + 1][j] + 1 == d[i + 1][j + 1]:
                        transit[(i + 1, j + 1)] = ('insert %s' % word2[j], (i+1, j))
                    else:
                        transit[(i + 1, j + 1)] = ('change %s to %s' % (word1[i], word2[j]), (i, j))

        ss1, ss2 = len(word1), len(word2)
        opt = []
        while ss1 > 0 and ss2 > 0:
            if (ss1, ss2) in transit:
                option, tup = transit[(ss1, ss2)]
                opt.append(option)
                ss1 = tup[0]
                ss2 = tup[1]
        opt.reverse()
        print('%s => %s:' % (word1, word2))
        for each in opt:
            print(each)
        return d[len(word1)][len(word2)]


solution = Solution()
assert solution.minDistance("horse", "ros") == 3
assert solution.minDistance(word1="intention", word2="execution") == 5
assert solution.minDistance_with_trip(word1="plasma", word2="altruism") == 6
# plasma => change p to a
# alasma => change a to t
# altsma => insert r
# altrsma => insert u
# altrusma => insert i
# altruisma => delete a
# altruism
